By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 15, Issue 4, pp. 903-1194

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

The Risch Differential Equation Problem

J. H. Davenport

pp. 903-918

BibTeX  Abstract Full Text:  PDF

Data Structures for Retrieval on Square Grids

Martin David Katz and Dennis J. Volper

pp. 919-931

BibTeX  Abstract Full Text:  PDF

Communication Complexity of Computing the Hamming Distance

King F. Pang and Abbas El Gamal

pp. 932-947

BibTeX  Abstract Full Text:  PDF

Improved Bounds for Matroid Partition and Intersection Algorithms

William H. Cunningham

pp. 948-957

BibTeX  Abstract Full Text:  PDF

An Inhomogeneity in the Structure of Karp Degrees

Klaus Ambos–Spies

pp. 958-963

BibTeX  Abstract Full Text:  PDF

Heaps on Heaps

Gaston H. Gonnet and J. Ian Munro

pp. 964-971

BibTeX  Abstract Full Text:  PDF

On Approximations and Incidence in Cylindrical Algebraic Decompositions

David Prill

pp. 972-993

BibTeX  Abstract Full Text:  PDF

Log Depth Circuits for Division and Related Problems

Paul W. Beame, Stephen A. Cook, and H. James Hoover

pp. 994-1003

BibTeX  Abstract Full Text:  PDF

On the Validity of the Direct Sum Conjecture

Joseph Ja'Ja' and Jean Takche

pp. 1004-1020

BibTeX  Abstract Full Text:  PDF

On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem

Norbert Blum

pp. 1021-1024

BibTeX  Abstract Full Text:  PDF

Ranking and Unranking of AVL-Trees

Liwu Li

pp. 1025-1035

BibTeX  Abstract Full Text:  PDF

A Simple Parallel Algorithm for the Maximal Independent Set Problem

Michael Luby

pp. 1036-1053

BibTeX  Abstract Full Text:  PDF

Finding a Maximum Clique in an Arbitrary Graph

Egon Balas and Chang Sung Yu

pp. 1054-1068

BibTeX  Abstract Full Text:  PDF

Average Case Analysis of Marking Algorithms

D. S. Hirschberg and L. L. Larmore

pp. 1069-1074

BibTeX  Abstract Full Text:  PDF

Searching in Trees, Series-Parallel and Interval Orders

U. Faigle, L. Lovász, R. Schrader, and Gy. Turán

pp. 1075-1084

BibTeX  Abstract Full Text:  PDF

Processor-Shared Time-Sharing Models in Heavy Traffic

Donald P. Gaver and Patricia A. Jacobs

pp. 1085-1100

BibTeX  Abstract Full Text:  PDF

Some Observations about the Randomness of Hard Problems

Dung T. Huynh

pp. 1101-1105

BibTeX  Abstract Full Text:  PDF

Probabilistic Analysis of Two Heuristics for the $3$-Satisfiability Problem

Ming-Te Chao and John Franco

pp. 1106-1118

BibTeX  Abstract Full Text:  PDF

Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

Tsuyoshi Kawaguchi and Seiki Kyan

pp. 1119-1129

BibTeX  Abstract Full Text:  PDF

On Maintaining Dynamic Information in a Concurrent Environment

Udi Manber

pp. 1130-1142

BibTeX  Abstract Full Text:  PDF

Sums of Divisors, Perfect Numbers and Factoring

Eric Bach, Gary Miller, and Jeffrey Shallit

pp. 1143-1154

BibTeX  Abstract Full Text:  PDF

Completion of a Set of Rules Modulo a Set of Equations

Jean-Pierre Jouannaud and Hélène Kirchner

pp. 1155-1194

BibTeX  Abstract Full Text:  PDF